/*
libfmail: Generic Search Tree implementation

Copyright (C) 2007  Carlos Daniel Ruvalcaba Valenzuela <clsdaniel@gmail.com>

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

typedef int (*HASH_FUNC)(char s);

class SearchNotFound {};

template <class T, int max> class TreeNode{
public:
    T value;
    TreeNode<T, max> *tree[max];
    
    TreeNode(){
        for (int i = 0; i < max; i++){
            tree[i] = NULL;
        }
    }
};

template <class T, int max, HASH_FUNC hash_func> class SearchTree{
private:
    TreeNode<T, max> *rootNode;
public:
    SearchTree(){
        rootNode = new TreeNode<T, max>();
    }
    int Insert(char *key, T value){
        int i, l, tk;
        TreeNode<T, max> *c;
        
        c = rootNode;
        l = strlen(key);
        
        for (i = 0; i < l; i++){
            tk = hash_func(key[i]);

            if (tk > max)
                printf("GOT MAX\n");
            
            if (c->tree[tk] == NULL)
                c->tree[tk] = new TreeNode<T, max>();
            c = c->tree[tk];
        }
        c->value = value;
        return 0;
    }
    T Lookup(char *key){
        int i, l, tk;
        TreeNode<T, max> *c;
        
        c = rootNode;
        l = strlen(key);
        
        for (i = 0; i < l; i++){
            tk = hash_func(key[i]);
            if (tk > max)
                throw SearchNotFound();
            
            if (tk == -1)
                break;
                
            if (c->tree[tk] == NULL)
                throw SearchNotFound();
                
            c = c->tree[tk];
        }
        
        return c->value;
    }
    
    int HasKey(char *key){
        int i, l, tk;
        TreeNode<T, max> *c;
        
        c = rootNode;
        for (i = 0; i < l; i++){
            tk = hash_func(key[i]);
            
            if (tk > max)
                return 0;
            
            if (tk == -1)
                break;
                
            if (c->tree[tk] == NULL)
                return 0;
                
            c = c->tree[tk];
        }
        
        return 1;
    }

};
